﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Engine.Sgml.Validation;
using Engine.Sgml.Merging;
using System.Diagnostics;

namespace Engine.Sgml.Allocation {
    internal sealed class InBlocksBlockAllocator : IBlockAllocator {

        public void Allocate(BlockItem item, AllocationContext context) {
            IList<InconsistentBlock> existingBlocks;
            if (context.Blocks.TryGetBlocks(item.Ancestor, out existingBlocks))
                AppendToExistingBlocks(item.InconsistentBlocks, existingBlocks);
            else
                context.Blocks.Add(item);
            }

        private static void AppendToExistingBlocks(IList<InconsistentBlock> unallocatedBlocks, IList<InconsistentBlock> existingBlocks) {
            if (existingBlocks.Count == 0) {
                for (int i = 0; i < unallocatedBlocks.Count; i++) {
                    existingBlocks.Add(unallocatedBlocks[i]);
                    }
                }
            else
                for (int i = 0; i < unallocatedBlocks.Count; i++) {
                    InconsistentBlock ub = unallocatedBlocks[i];
                    int blocksCount = existingBlocks.Count;
                    int midline = blocksCount / 2;
                    do {
                        InconsistentBlock eb = existingBlocks[midline];
                        if (eb.EndIndex - ub.StartIndex == -1) {
                            for (int j = 0; j < ub.Count; j++) {
                                eb.Add(ub[j]);
                                }
                            break;
                            }
                        else if (ub.EndIndex - eb.StartIndex == 1) {
                            for (int j = 0; j < ub.Count; j++) {
                                eb.Insert(j, ub[j]);
                                }
                            break;
                            }
                        else if (eb.EndIndex < ub.StartIndex) {
                            if (blocksCount - midline == 1) {
                                existingBlocks.Insert(midline + 1, ub);
                                break;
                                }
                            midline = midline + ((blocksCount - midline) / 2);
                            }
                        else if (ub.EndIndex < eb.StartIndex) {
                            if (midline == 0) {
                                existingBlocks.Insert(midline, ub);
                                break;
                                }
                            blocksCount = midline;
                            midline /= 2;
                            }
                        } while (true);
                    }
#if DEBUG
            for (int i = 1; i < existingBlocks.Count; i++) {
                Debug.Assert(existingBlocks[i - 1].StartIndex <= existingBlocks[i - 1].EndIndex);
                Debug.Assert(existingBlocks[i].StartIndex <= existingBlocks[i].EndIndex);
                Debug.Assert(existingBlocks[i - 1].EndIndex < existingBlocks[i].StartIndex);
                Debug.Assert(existingBlocks[i].StartIndex - existingBlocks[i - 1].EndIndex > 1);
                }
#endif
            }
        }
    }
